//
// Created by Liming Shao on 11/3/2017.
//

#include <cstdlib>
#include "B035.h"
#include <iostream>
using namespace std;

Node* B035::removeLastKthNode(Node *head, int lastKth) {
    Node *cur = head;
    Node *ret = head;

    if(lastKth < 1){
        cout << "K is invalid" << endl;
    }

    for (int i = 0; i < lastKth-1 && cur != nullptr; ++i) {
        cur = cur->next;
    }

    // K大于链表长度，返回头结点
    if (cur == nullptr){
        cout << "K is invalid" << endl;
        return head;
    }

    // K等于链表长度，删除第一个节点，返回第二个节点指针
    if(cur->next== nullptr){
        return head->next;
    }

    Node *tmp;
    while(cur->next != nullptr){
        cur = cur->next;
        tmp = ret;
        ret = ret->next;
    }

    tmp->next = ret->next;

    cout << "Delete " << ret->value << endl;
    free(ret);

    return head;
}

DoubleNode* B035::removeLastKthNode(DoubleNode *head, int lastKth) {
    DoubleNode *cur = head;
    DoubleNode *ret = head;

    if(lastKth < 1){
        cout << "K is invalid" << endl;
    }

    for (int i = 0; i < lastKth-1 && cur != nullptr; ++i) {
        cur = cur->next;
    }

    // K大于链表长度，返回头结点
    if (cur == nullptr){
        cout << "K is invalid" << endl;
        return head;
    }

    // K等于链表长度，返回第二个节点指针
    if(cur->next== nullptr){
        return head->next;
    }

    while(cur->next != nullptr){
        cur = cur->next;
        ret = ret->next;
    }

    ret->pre->next = ret->next;
    // K==1
    if(ret->next!= nullptr)
        ret->next->pre = ret->pre;

    cout << "Delete " << ret->value << endl;
    free(ret);

    return head;
}


Node *B035::addNode(Node *head, int value) {
    auto *tmp = (Node*)malloc(sizeof(Node));
    tmp->value = value;
    tmp->next = nullptr;

    if(head != nullptr){
        while(head->next != nullptr){
            head = head->next;
        }
        head->next = tmp;
    }

    return tmp;
}

DoubleNode *B035::addNode(DoubleNode *head, int value) {
    auto *tmp = (DoubleNode*)malloc(sizeof(DoubleNode));
    tmp->value = value;
    tmp->next = nullptr;
    tmp->pre = nullptr;

    if(head != nullptr){
        while(head->next != nullptr){
            head = head->next;
        }
        head->next = tmp;
        tmp->pre = head;
    }

    return tmp;
}

void B035::printList(Node *head) {
    while(head != nullptr){
        cout << head->value << " ";
        head = head->next;
    }
    cout << endl;
}

void B035::printList(DoubleNode *head) {
    while(head != nullptr){
        cout << head->value << " ";
        head = head->next;
    }
    cout << endl;
}

void B035::test() {
    // 构建单链表
    Node* firstList = addNode((Node*)nullptr, 1);
    for (int i = 0; i < 17; ++i) {
        addNode(firstList, i+2);
    }

    printList(firstList);
    firstList = removeLastKthNode(firstList,2);
    printList(firstList);

    // 构建双链表
    DoubleNode* secondList = addNode((DoubleNode*)nullptr, 10);
    for (int i = 0; i < 6; ++i) {
        addNode(secondList, i+11);
    }
    printList(secondList);
    secondList = removeLastKthNode(secondList, 7);
    printList(secondList);

}